This invention relates generally to computer networks comprising a plurality of stations that communicate data in a ring using a token-based protocol, and, more specifically, to a mechanism for removing information frames from the network.
A computer network enables various devices, such as processors, mass storage devices, and printers, to communicate with each other over high speed communication links. The devices are connected or interfaced to the network, and thus transfer data to and from the network, through stations. The stations are interconnected by communication links in a manner that defines the network topology.
One example of such a network is a Local Area Network (LAN). A LAN allows high-bandwidth communication among devices within a limited geographical area. The communication links typically include optical fibers, coaxial cables, or twisted conductor pairs.
LANs may be configured using any of a number of topologies, for example, buses or rings. In a network configured as a bus, data signals are usually communicated along a bus in both directions from an originating station. In a network configured as a ring, network stations transmit data around the ring in one direction. Thus, when a station transmits data onto the ring, the data signals travel around the ring from station to station, with each station receiving the data signals from the preceding station and repeating them to the succeeding station, until the data signals reach the station that is to receive them. In a well known ring network, the receiving, or destination, station also repeats the data to its downstream successor, and the data signals thus continue around the ring to the originating, or source, station. Each source station strips its own frames from the ring.
Network stations transmit and receive data in the form of frames. The frames contain, in addition to the data, addresses, an error detection sequence and status flags, such as a flag indicating receipt of the frame by the intended receiving, or destination, station. The frame addresses identify the source station and the destination station or stations.
Every station and every attached device are each identified by a unique address. Thus each station has associated with it its unique station address and the addresses of its attached devices. The stations may also have other addresses associated with them. A frame directed from a source station to a single destination station thus contains the address of the source station and, for example, the address of a specific device attached to the destination station. Each station may maintain a list of its associated addresses, such that the station receives the frames containing any one of its addresses.
A destination station, in addition to repeating a received frame to its succeeding station, copies the frame for use by the appropriate device(s) associated with the station. The destination station may also set the applicable status flags indicating receipt of the frame.
When a frame has returned to its source location, the source station, recognizing the source address in the frame as its own, removes, or strips, the frame from the ring data stream. The present invention is concerned with the orderly stripping of frames from the network, to ensure that unwanted frames of data do not accumulate, as a result of "understripping," and that frames destined for other stations are not inadvertently stripped from the ring, as a result of "overstripping."
The stations operate in accordance with communication protocols that facilitate the orderly transfer of information frames over the communication links. One type of communication protocol is a token ring system. Such systems use a token, that is, a specific string of bits in the form of a special frame, to indicate that a transmitting station has completed its transmission. A succeeding station may then, following the dictates of the protocol, begin transmitting frames upon receipt of the token.
In a token ring system, a station may not transmit data over the ring unless it holds the token. Thus if a station has frames to transmit around the ring it first removes the token from the ring data stream, that is, the station "captures" the token, when it is received from a preceding or upstream station. The capturing station then begins its transmission of information frames. When the station is finished with the information frame transmission it retransmits the token, effectively releasing it. The succeeding stations thereafter transfer the token around the ring until a station captures it in order to make a transmission. Various mechanisms ensure fairness of access, limiting the number of frames that can be transmitted by a station on capturing the token.
Two or more rings, or more generally, two or more LANs, may be connected by a bridge, which is a special purpose station simultaneously connected to multiple LANs, to form an extended LAN. The bridge thus facilitates communication between a transmitting station on, for example, one of the rings and a receiving station on another ring. The bridge functions as a destination station on the ring containing the transmitting station and copies the frames directed to a second ring, while also repeating these frames on the source station ring. The bridge also functions as a transmitting station on the second ring and transmits the copied frames in that ring after capturing the ring's token. The second ring may contain the destination station, or it may be an intermediate ring containing a bridge to another LAN, which may, in turn, contain the destination station or be another intermediate LAN.
There are two basic modes of bridge operation: transparent and non-transparent. A bridge operating transparently transmits the frames originated by the source station without significantly altering them, that is, without changing any portion of a frame that is protected by the frame's error detection sequence. Alternatively, a bridge operating non-transparently significantly alters the frames originated by the source station before transmitting them to the connected LAN. A non-transparent bridge may, for example, alter the source address to the address of the bridge on the second ring or it may alter certain other information in the frame.
The non-transparent bridge must recalculate and replace the error detection sequence contained in each of the frames to prevent the frame alterations from being treated as errors. However, if the bridge incorrectly copies a frame or inadvertently copies an erroneous frame, alters it, introduces an error inside the bridge, and then recalculates the error detection sequence, it may render the frame errors undetectable. Therefore, the integrity of the frame information is considered to be reduced in non-transparent bridge operation.
The bridge, regardless of the mode in which it operates, must strip from the second ring the frames it transmits. Typically, a station "recognizes" the source address in that frame as its own address and strips the frame. A bridge that leaves the addresses unaltered, and which is not the original source station, may not recognize the source address in the frames it has transmitted over the second ring. The bridge is capable of transmitting frames that were originally transmitted by one of many source stations on one or more different LANs. When the frames return to the bridge over the second ring, the bridge may not have time to compare the frame source address with the addresses of the many source stations on the various LANs before the decision to strip must be made. Thus the bridge could repeat a frame that should be stripped by it. This problem is aggravated by the large number of stations or nodes, typically tens of thousands, that may be included in an extended LAN. The complexity and cost of maintaining a database of all such stations, merely to facilitate frame stripping, provide another important reason to seek an alternative solution to the frame stripping problem, i.e. to determine which frames to strip.
One possible method for stripping frames involves having the bridge mark the last frame in the sequence of transmitted frames, e.g. by setting a flag in the frame. The bridge then, after a transmission, strips the frames it receives over the ring until it detects the set flag in one of the frames. If, however, the frame containing the flag is lost or corrupted, making the set flag undetectable, the bridge may continue to strip the frames it receives over the ring until it is signalled to stop, for example, by the expiration of a locally kept timer. The bridge would thus strip frames originated by other stations on the extended LAN, preventing the frames from reaching their intended destinations. If the flag is a single-bit flag, a bit-error in the frame may result in the flag appearing reset, and in this case the bridge would stop stripping before it had removed all of its frames.
A non-bridge station that connects many devices to the LAN may also have difficulty determining which frames it should strip. Such a station must determine whether to strip a frame within the time it takes the frame to pass through the station. Thus the station may not have time to match the frame source address with one of its many associated addresses, and another method for determining which frames to strip must be used. As mentioned above, the cost and complexity of maintaining a large database for frame stripping purposes are extremely high.
The solution to this problem proposed in the cross-referenced application is for each station to keep a count of the frames transmitted, and to transmit one or more coded marker frames following all the messages transmitted by a station and immediately prior to transmitting the token. After a transmission is begun, the station strips from the ring the frames it next receives, decrementing the count for each properly stripped (i.e., error free) frame, until either the count is reduced to zero, or one of its marker frames is detected. Although this basic technique performs satisfactorily in most conditions, it is slow to correct the problem that arises when dealing with the existence of multiple extraneous No-Owner Frames, i.e. frames that circulate about the ring network and are not recognized by any stations as candidates for stripping. Frames of this type can be generated in a number of ways. For example, a station may transmit multiple information frames and be removed from the network before there is time for it to strip the frames. Or, if a duplicate token is erroneously generated by a network noise error, a station may erroneously terminate stripping upon receiving this second token, leaving its transmitted information frames circulating as No-Owner Frames. The second token may eventually be stripped, when it reaches a station that already has the real token. Similarly, these No-Owner Frames may also be eventually stripped. However, in the meantime considerable overhead is incurred at the destination station.
If multiple No-Owner Frames are received while a station is in a stripping mode, they will be stripped from the ring until the frame count is decremented to zero. This will terminate stripping and leave some or all of the station's information frames still circulating as new No-Owner Frames.
A related difficulty is the occurrence of stripping errors, particularly understripping errors, wherein a station prematurely terminates stripping of information frames, when a second, erroneously generated, token is received by a station that is presently stripping frames and does not hold the real token. The cross-referenced application provides no way of detecting such errors.
Another difficulty with the solution proposed in the cross-referenced application is that, depending on the size of the network, the frame counter required may have to be relatively large, thereby increasing the cost and complexity of the station.
It will be appreciated from the foregoing that there is room for further improvement in the techniques proposed in our prior application. Although the present invention involves improvements over the invention defined by the prior application cross-referenced above, the prior application is not believed to be prior art to the present invention.